package com.jwetherell.my.problems.patternsearching;


public class Solution {

	public static void main(String[] args) {

		Solution solution = new Solution();

		Node<Integer> head = null;
		head = solution.insertAtHead(head, 2);
		head = solution.insertAtHead(head, 4);
		head = solution.insertAtHead(head, 8);
		head = solution.insertAtHead(head, 10);

		System.out.println("Linked list before reversal: ");
		solution.printLinkedList(head);

		head = solution.reverseLinkedList(head);

		System.out.println("\nLinked list after reversal:");
		solution.printLinkedList(head);

	}
	
	static class Node<T extends Comparable<T>> {

		public Node<T> previous;
		public Node<T> next;
		public T data;

		public Node(T data) {
			this.data = data;
		}

	}

	private <T extends Comparable<T>> Node<T> reverseLinkedList(Node<T> head) {
		Node<T> temp = null;
		Node<T> current = head;

		while (current != null) {
			temp = current.previous;
			current.previous = current.next;
			current.next = temp;
			current = current.previous;
		}

		if (temp != null)
			head = temp.previous;

		return head;
	}

	private <T extends Comparable<T>> Node<T> insertAtHead(Node<T> head,
			T data) {
		
		Node<T> newNode = new Node<T>(data);
		newNode.previous = null;
		newNode.next = head;

		if (head != null)
			head.previous = newNode;

		return newNode;
	}

	private <T extends Comparable<T>> void printLinkedList(Node<T> node) {
		while (node != null) {
			System.out.print(node.data + " ");
			node = node.next;
		}
	}


}